package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/5/12 9:16
 */
public class C1310 {

    // 先写个暴力解, 验
    public static int[] xorQueries(int[] arr, int[][] queries) {
        int N = queries.length;
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            int[] query = queries[i];
            int ans = 0;
            for (int j = query[0]; j <= query[1]; j++) {
                ans ^= arr[j];
            }
            res[i] = ans;
        }
        return res;
    }

    // 预处理, 想要快速的查出 i~j的异或和. 那我们可以先预处理出一个前缀异或和数组
    // i~j的异或和 = sum[j] - sum[i - 1].
    // 为了边界好处理, 第0位多补一位. 即i~j的异或和 = sum[j + 1] - sum[i].
    public static int[] xorQueries2(int[] arr, int[][] queries) {
        int len = arr.length;
        int N = queries.length;
        int[] res = new int[N];
        int[] sum = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            sum[i] = arr[i - 1] ^ sum[i - 1];
        }
        for (int i = 0; i < N; i++) {
            int start = queries[i][0];
            int end = queries[i][1];
            res[i] = sum[end + 1] ^ sum[start];
        }
        return res;
    }


    // for test
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 8};
        int[][] queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};

        System.out.println(Arrays.toString(xorQueries(arr, queries)));
        System.out.println(Arrays.toString(xorQueries2(arr, queries)));
        ;
    }

}
